决策树(ID3 & C4.5 & CART)及正则剪枝

发表于 | 分类于 | | 次阅读

1、介绍

决策树（Decision Tree）的思想是贪心(最优化分)与分治(子树划分)。构建决策树的目的是：随着划分过程的进行，使得决策树分支结点所包含的样本尽可能属于同一类别，即使得分类更准确。下图给出了一个决策树的简单例子:
决策树的列子
决策树模型在监督学习中非常常见，可用于分类（二分类、多分类）和回归。虽然将多棵弱决策树的Random Forest、GBDT等tree ensembel 模型更为常见，但是“完全生长”决策树因为其简单直观，具有很强的解释性，也有广泛的应用，而且决策树是tree ensemble 的基础，值得好好理解。一般而言一棵“完全生长”的决策树包含，特征选择、决策树构建、剪枝三个过程，本文主要介绍ID3、C4.5和CART这三种构造决策树的算法以及简要介绍树模型的正则和剪枝。

决策树的优点和缺点
优点：

  • 决策树算法中学习简单的决策规则建立决策树模型的过程非常容易理解，
  • 决策树模型可以可视化，非常直观
  • 应用范围广，可用于分类和回归，而且非常容易做多类别的分类
  • 能够处理数值型和连续的样本特征

缺点：

  • 很容易在训练数据中生成复杂的树结构，造成过拟合（overfitting）。剪枝可以缓解过拟合的负作用，常用方法是限制树的高度、叶子节点中的最少样本数量。
  • 学习一棵最优的决策树被认为是NP-Complete问题。实际中的决策树是基于启发式的贪心算法建立的，这种算法不能保证建立全局最优的决策树。Random Forest 引入随机能缓解这个问题

2、ID3算法

ID3算法最早是由罗斯昆（J. Ross Quinlan）于1975年在悉尼大学提出的一种分类预测算法，算法的核心是“信息熵”。ID3算法通过计算每个属性的信息增益，认为信息增益高的是好属性，每次划分选取信息增益最高的属性为划分标准，重复这个过程，直至生成一个能完美分类训练样例的决策树。

2.1、信息熵

熵这个概念最早起源于物理学，在物理学中是用来度量一个热力学系统的无序程度，而在信息学里面，熵是对不确定性的度量。在1948年，香农引入了信息熵（information entropy），将其定义为离散随机事件出现的概率，一个系统越是有序，信息熵就越低，反之一个系统越是混乱，它的信息熵就越高。所以信息熵可以被认为是系统有序化程度的一个度量。
对于有K个类别的分类问题来说，假定样本集合D中第 k 类样本所占的比例为$p_{k}(k=1,2,…,K)$,则样本集合D的信息熵定义为:
$$
H(D)=-\sum_{k=1}^{K}p_{k}log_{2}p_{k}
$$

2.2、信息增益

定义：特征A对于数据集合D的信息增益为g(D,A),定义为集合D的经验熵H(D)与特征A给定条件下集合D的条件熵H(D|A)只差，即
$$
g(D,A)=H(D)-H(D|A)
$$
一般的，熵H(D)与条件熵H(D|A)之差称为互信息，决策树学习中的信息增益等价于数据集中类与特征的互信息。
通过以下例子计算信息增益:
sample1
计算过程树下：
(1) 首先计算经验熵H(D):
$$
H(D)=-\frac{9}{15}log_{2}\frac{9}{15}-\frac{6}{15}log_{2}\frac{6}{15}=0.971
$$
(2) 计算各特征对于数据集合D的信息增益，分别以$A_{1}、A_{2}、A_{3}、A_{4}$分别表示年龄、有工作、有自己的房子和信贷情况4个特征，则计算如下：
计算$A_1$
$$
\begin{split}
g(D,A_{1}){} &=H(D)-[\frac{5}{15}H(D_{1})+\frac{5}{15}H(D_{2})+\frac{5}{15}H(D_{3})] \\
{} &=0.971-[\frac{5}{15}(-\frac{2}{5}log_{2}\frac{2}{5}-\frac{3}{5}log_{2}\frac{3}{5}) \\
{} & \quad +\frac{5}{15}(-\frac{3}{5}log_{2}\frac{3}{5}-\frac{2}{5}log_{2}\frac{2}{5}) \\
{} & \quad +\frac{5}{15}(-\frac{1}{5}log_{2}\frac{1}{5}-\frac{4}{5}log_{2}\frac{4}{5})] \\
{} &=0.971-0.888=0.083
\end{split}
$$
这里的$A_{1}、A_{2}、A_{3}$分别是D中取值为青年、中年、老年的样本子集。
类似的计算$A_{2}、A_{3}、A_{4}$，结果如下：
$$
\begin{split}
g(D,A_{2}){} &=H(D)-[\frac{5}{15}H(D_{1})+\frac{10}{15}H(D_{2})]=0.324 \\
g(D,A_{3}){} &=0.420 \\
g(D,A_{4}){} &=0.363
\end{split}
$$
最后,比较各特征的信息增益，由于特征$A_3$(有自己的房子)的信息增益值最大，所以选择$A_3$做为最优特征。

2.3、算法流程和思想

ID3算法流程如下：
输入：数据集D，特征集A，阈值$\varepsilon$
输出：决策树T

  • (1) 若D中的所有实例都属于同一类$C_{k}$,则T为单节点树，并将类$C_{k}$做为该节点的类标记，返回T；
  • (2) 若$A=\phi$，则T为单节点树，并将D中实例最大的类$C_{k}$做为该节点的类标记，返回T；
  • (3) 否则按照上述例子计算A中各特征对D的信息增益，选择信息增益最大的特征$A_{g}$；
  • (4) 如果$A_{g}$的信息增益小于阈值$\varepsilon$，则置T为单节点树，并将D中实例数最大的类$C_{k}$作为该节点的类标记，返回T;
  • (5) 否则，对$A_{g}$的每一个可能只$a_{i}$，依据$A_{g}=a_{i}$将D分割若干非空子集$D_{i}$,将$D_{i}$中实例数最大的类作为标记，构建子结点，由结点及其子结点构成树T，返回T；
  • (6) 对第i个子结点，以$D_{i}$为训练集，以$A-A_{g}$为特征集，递归的调用(1)~(5)步，得到子树$T_{i}$,返回$T_{i}$。

ID3算法的基本思想是：
首先计算出原始数据集的信息熵，然后依次将数据中的每一个特征作为分支标准，并计算其相对于原始数据的信息增益，选择最大信息增益的分支标准来划分数据，因为信息增益越大，区分样本的能力就越强，越具有代表性。重复上述过程从而生成一棵决策树，很显然这是一种自顶向下的贪心策略。

3、C4.5算法

ID3中使用信息增益其实是有一个缺点，那就是它偏向于具有大量值的属性–就是说在训练集中，某个属性所取的不同值的个数越多，那么越有可能拿它来作为分裂属性，而这样做有时候是没有意义的。所以在ID3算法上进行改进，C4.5使用了信息增益比来进行特征选择。

3.1、信息增益比

信息增益值的大小是相对于训练数据集而言，并无绝对的意义，在分类问题困难时，也就是说在训练数据集的经验熵大的时候，信息增益值会偏大，反之，信息增益值会变小。使用信息增益比可以对这一问题进行校正。
定义： 特征集A对训练集D的信息增益比$g_{R}(D,A)$定义为其信息增益$g(D,A)$与训练数据集D的经验熵H(D)之比：
$$
g_{R}(D,A)=\frac{g(D,A)}{H(D)}
$$

3.2、算法流程和思想

C4.5的算法流程和ID3的算法流程一致，只是选取特征的方式不同。
C4.5算法思想
C4.5算法是对ID3算法的改进，C4.5克服了ID3的2个缺点：

  • 用信息增益选择属性时偏向于选择分枝比较多的属性值，即取值多的属性
  • 不能处理连续属性

注意:

  • 增益率准则对可取值数目较少的属性有所偏好，因此C4.5算法并不是直接选择增益率最大的属性作为分支标准，而是先从候选属性中找出信息增益高于平均水平的属性，再从中选择增益率最高的。
  • C4.5算法处理连续属性的方法是先把连续属性转换为离散属性再进行处理。虽然本质上属性的取值是连续的，但对于有限的采样数据它是离散的

4、CART算法

CART（Classification And Regression Tree）算法既可以用于创建分类树，也可以用于创建回归树。CART算法的重要特点包含以下三个方面：

  • 二分(Binary Split)：在每次判断过程中，都是对样本数据进行二分。CART算法是一种二分递归分割技术，把当前样本划分为两个子样本，使得生成的每个非叶子结点都有两个分支，因此CART算法生成的决策树是结构简洁的二叉树。由于CART算法构成的是一个二叉树，它在每一步的决策时只能是“是”或者“否”，即使一个feature有多个取值，也是把数据分为两部分
  • 单变量分割(Split Based on One Variable)：每次最优划分都是针对单个变量。
  • 剪枝策略：CART算法的关键点，也是整个Tree-Based算法的关键步骤。剪枝过程特别重要，所以在最优决策树生成过程中占有重要地位。有研究表明，剪枝过程的重要性要比树生成过程更为重要，对于不同的划分标准生成的最大树(Maximum Tree)，在剪枝之后都能够保留最重要的属性划分，差别不大。反而是剪枝方法对于最优树的生成更为关键。
    CART树生成就是递归的构建二叉决策树的过程，对回归使用平方误差最小化准则，对于分类树使用基尼指数(Gini index)准则，进行特征选择，生成二叉树。

4.1、回归树

CART回归树预测回归连续型数据，假设X与Y分别是输入和输出变量，并且Y是连续变量。在训练数据集所在的输入空间中，递归的将每个区域划分为两个子区域并决定每个子区域上的输出值，构建二叉决策树。
$$
D={(x_{1},y_{1}),(x_{2},y_{2}),(x_{3},y_{3})….,(x_{n},y_{n})}
$$

选择最优切分变量j与切分点s： 遍历变量j，对规定的切分变量j扫描切分点s，选择使下式得到最小值时的(j,s)对。其中$R_m$是被划分的输入空间，$c_m$是空间$R_m$对应的固定输出值。
$$
min_{j,s}\big[min_{c_{i}}\sum_{x_{i} \in R_{i}(j,s)}(y_{i}-c_{i})^2 + min_{c_{2}}\sum_{x_{i} \in R_{i}(j,s)}(y_{i}-c_{1})^2\big]
$$

用选定的(j,s)对，划分区域并决定相应的输出值:
$$
R_{1}(j,s)={x|x^{(j)} \leq s},R_{2}(j,s)={x|x^{(j)} > s} \\
\hat{c}_{m} = \frac{1}{N_{m}}\sum_{x_{i} \in R_{m}(j,s)} y_{i} \\
x \in R_{m},m=1,2,…..
$$
继续对两个子区域调用上述步骤，将输入空间划分为M个区域R1,R2,…,Rm，生成决策树。
$$
f(x)=\sum_{m=1}^{M}\hat{c}_{m}I(x\in R_{m})
$$
当输入空间划分确定时，可以用 平方误差 来表示回归树对于训练数据的预测方法，用 平方误差 最小的准则求解每个单元上的最优输出值。
$$
\sum_{x_{i} \in R_{m}}(y_{i}-f(x_{i}))^2
$$

实例计算
考虑下图所示的连续性变量，根据给定的数据点，考虑1.5,2.5,3.5,4.5,5.5,6.5,7.5,8.5,9.5切分点。对各切分点依次求出$R_1$,$R_2$,$c_1$,$c_2$及m(s)。
CART树例子表格01
例如当切分点s=1.5时，得到R1={1},R2={2,3,4,5,6,7,8,9,10}，其中$c_1$,$c_2$,m(s)计算如下所示：
CART树例子表格02
依次改变(j,s)对，可以得到s及m(s)的计算结果，如下表所示。
CART树例子表格03
当x=6.5时，此时R1={1,2,3,4,5,6},R2={7,8,9,10},c1=6.24,c2=8.9。回归树$T_{1}(x)$为
CART树例子表格04
然后我们利用$f_{1}(x)$拟合训练数据的残差，如下表所示
CART树例子表格05
用f1(x)拟合训练数据得到平方误差
CART树例子表格06
第二步求$T_{2}(x)$与求$T_{1}(x)$方法相同，只是拟合的数据是上表的残差。可以得到
CART树例子表格07
用f2(x)拟合训练数据的平方误差
CART树例子表格08
继续求得$T_3(x)、T_4(x)、T_5(x)、T_6(x)$，如下所示
CART树例子表格09
用$f_6(x)$拟合训练数据的平方损失误差如下所示，假设此时已经满足误差要求，那么$f(x)=f_6(x)$便是所求的回归树。
CART树例子表格10

4.2、分类树

CART分类树预测分类离散型数据，采用基尼指数选择最优特征，同时决定该特征的最优二值切分点。分类过程中，假设有K个类，样本点属于第k个类的概率为$p_k$，则概率分布的基尼指数定义为:
CART树例子表格11
根据基尼指数定义，可以得到样本集合D的基尼指数，其中$C_k$表示数据集D中属于第k类的样本子集。
CART树例子表格12
如果数据集D根据特征A在某一取值a上进行分割，得到$D_1,D_2$两部分后，那么在特征A下集合D的基尼系数如下所示。其中基尼系数Gini(D)表示集合D的不确定性，基尼系数Gini(D,A)表示A=a分割后集合D的不确定性。基尼指数越大，样本集合的不确定性越大。
CART树例子表格13
对于属性A，分别计算任意属性值将数据集划分为两部分之后的Gain_Gini，选取其中的最小值，作为属性A得到的最优二分方案。然后对于训练集S，计算所有属性的最优二分方案，选取其中的最小值，作为样本及S的最优二分方案。
CART树例子表格14

其中算法的停止条件有：

  • 1、节点中的样本个数小于预定阈值，
  • 2、样本集的Gini系数小于预定阈值（此时样本基本属于同一类），
  • 3、或没有更多特征。

实例计算
CART树例子表格15
针对上述离散型数据，按照体温为恒温和非恒温进行划分。其中恒温时包括哺乳类5个、鸟类2个，非恒温时包括爬行类3个、鱼类3个、两栖类2个，如下所示我们计算$D_1,D_2$的基尼指数。
CART树例子表格16
然后计算得到特征体温下数据集的Gini指数，最后我们选择Gain_Gini最小的特征和相应的划分。
CART树例子表格17

4.3、分类树 VS 回归树

提到决策树算法，很多想到的就是上面提到的ID3、C4.5、CART分类决策树。其实决策树分为分类树和回归树，前者用于分类，如晴天/阴天/雨天、用户性别、邮件是否是垃圾邮件，后者用于预测实数值，如明天的温度、用户的年龄等。

作为对比，先说分类树，我们知道ID3、C4.5分类树在每次分枝时，是穷举每一个特征属性的每一个阈值，找到使得按照feature<=阈值，和feature>阈值分成的两个分枝的熵最大的feature和阈值。按照该标准分枝得到两个新节点，用同样方法继续分枝直到所有人都被分入性别唯一的叶子节点，或达到预设的终止条件，若最终叶子节点中的性别不唯一，则以多数人的性别作为该叶子节点的性别。

回归树总体流程也是类似，不过在每个节点（不一定是叶子节点）都会得一个预测值，以年龄为例，该预测值等于属于这个节点的所有人年龄的平均值。分枝时穷举每一个feature的每个阈值找最好的分割点，但衡量最好的标准不再是最大熵，而是最小化均方差–即（每个人的年龄-预测年龄）^2 的总和 / N，或者说是每个人的预测误差平方和 除以 N。这很好理解，被预测出错的人数越多，错的越离谱，均方差就越大，通过最小化均方差能够找到最靠谱的分枝依据。分枝直到每个叶子节点上人的年龄都唯一（这太难了）或者达到预设的终止条件（如叶子个数上限），若最终叶子节点上人的年龄不唯一，则以该节点上所有人的平均年龄做为该叶子节点的预测年龄。

5、正则和剪枝

树剪枝和CART剪枝
决策树很容易发生过拟合，可以改善的方法有：

  • 1、通过阈值控制终止条件，避免树形结构分支过细。
  • 2、通过对已经形成的决策树进行剪枝来避免过拟合。
  • 3、基于Bootstrap的思想建立随机森林。

剪枝(pruning)是解决决策树过拟合的主要手段，通过剪枝可以大大提升决策树的泛化能力。通常，剪枝处理可分为：预剪枝，后剪枝。

  • 预剪枝：通过启发式方法，在生成决策树过程中对划分进行预测，若当前结点的划分不能对决策树泛化性能提升，则停止划分，并将其标记为叶节点
  • 后剪枝：对已有的决策树，自底向上的对非叶结点进行考察，若该结点对应的子树替换为叶结点能提升决策树的泛化能力，则将改子树替换为叶结点

6、决策树算法总结

上面我们对CART算法做了一个详细的介绍，CART算法相比C4.5算法的分类方法，采用了简化的二叉树模型，同时特征选择采用了近似的基尼系数来简化计算。当然CART树最大的好处是还可以做回归模型，这个C4.5没有。下表给出了ID3，C4.5和CART的一个比较总结。希望可以帮助大家理解。

算法 支持模型 树结构 特征选择 连续值处理 缺失值处理 剪枝
ID3 分类 多叉树 信息增益 不支持 不支持 不支持
C4.5 分类 多叉树 信息增益比 支持 支持 支持
CART 分类，回归 二叉树 基尼系数，均方差 支持 支持 支持

看起来CART算法高大上，那么CART算法还有没有什么缺点呢？有！主要的缺点我认为如下：

  • 1）应该大家有注意到，无论是ID3, C4.5还是CART,在做特征选择的时候都是选择最优的一个特征来做分类决策，但是大多数，分类决策不应该是由某一个特征决定的，而是应该由一组特征决定的。这样决策得到的决策树更加准确。这个决策树叫做多变量决策树(multi-variate decision tree)。在选择最优特征的时候，多变量决策树不是选择某一个最优特征，而是选择最优的一个特征线性组合来做决策。这个算法的代表是OC1，这里不多介绍。
  • 2）如果样本发生一点点的改动，就会导致树结构的剧烈改变。这个可以通过集成学习里面的随机森林之类的方法解决。　　　

7、参考